#include <stdio.h>
typedef struct BSTreeNode
{
    int m_nValue;
    struct BSTreeNode *m_pLeft;
    struct BSTreeNode *m_pRight;
}BSTreeNode;

void helper(BSTreeNode*&, BSTreeNode*&, BSTreeNode*&);

BSTreeNode* treeToLinkdList(BSTreeNode * root)
{
    BSTreeNode * head, * tail;
    helper(head, tail, root);
    return head;
}

void helper(BSTreeNode*& head, BSTreeNode*& tail, BSTreeNode*& root)
{
    BSTreeNode *lt, *rh;
    if( root == NULL )
    {
	head = NULL, tail = NULL;
	return;
    }
    helper(head, lt, root->m_pLeft);
    helper(rh, tail, root->m_pRight);
    if(lt != NULL)
    {
	lt->m_pRight = root;
	root->m_pLeft = lt;
    } else {
	head = root;
    }
    if(rh != NULL){
	root->m_pRight = rh;
	rh->m_pLeft = root;
    } else {
	tail = root;
    }
}

void print(BSTreeNode * head)
{
    if(head != NULL){
	printf("[%d]", head->m_nValue);
	print(head->m_pLeft);
	print(head->m_pRight);
    }
}
void print_d(BSTreeNode * head)
{
    printf("\n");
    BSTreeNode* prev;
    while(head != NULL)
    {
	prev = head;
	printf("[%d]", head->m_nValue);
	head = head->m_pRight;
    }
    printf("\n");

    while(prev != NULL)
    {
	printf("[%d]", prev->m_nValue);
	prev = prev->m_pLeft;
    }
}
int main()
{
    BSTreeNode m4, m6, m8, m10, m12, m14, m16;
    m4.m_nValue = 4;
    m4.m_pLeft = m4.m_pRight = NULL;

    m8.m_nValue = 8;
    m8.m_pLeft = m8.m_pRight = NULL;

    m12.m_nValue = 12;
    m12.m_pLeft = m12.m_pRight = NULL;

    m16.m_nValue = 16;
    m16.m_pLeft = m16.m_pRight = NULL;

    m6.m_nValue = 6;
    m6.m_pLeft = &m4; m6.m_pRight = &m8;

    m14.m_nValue = 14;
    m14.m_pLeft = &m12; m14.m_pRight = &m16;

    m10.m_nValue = 10;
    m10.m_pLeft = &m6; m10.m_pRight = &m14;

    print(&m10);
    print_d(treeToLinkdList(&m10));
    
}
